package leetcode.offer_two_special.tree;

import leetcode.tree.common.TreeNode;

import java.util.HashMap;

/**
 * @author mazouri
 * @create 2021-09-12 16:58
 */
public class _50_pathSum {
    int targetSum;
    //key:pathSum value:count
    HashMap<Integer, Integer> map = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        map.put(0, 1);

        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int path) {
        if (root == null) return 0;

        path += root.val;
        Integer count = map.getOrDefault(path - targetSum, 0);
        map.put(path, map.getOrDefault(path, 0) + 1);

        count += dfs(root.left, path);
        count += dfs(root.right, path);
        //函数结束时，程序将回到节点的父节点，因此需要在函数结束前将当前节点删除
        map.put(path, map.get(path) - 1);
        return count;
    }
}
